package argo.hot100.heap;

public class FindKthLargest {

    public int findKthLargest(int[] nums, int k) {

        return quickFind(nums, 0, nums.length - 1, nums.length - k);

    }


    public int quickFind(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[k];
        }

        int x = nums[left], l = left - 1, r = right + 1;
        while (l < r) {
            do {
                l++;
            } while (nums[l] > x);
            do {
                r--;
            } while (nums[r] < x);

            if (l < r) {
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
            }

        }

        if (k <= r) {
            return quickFind(nums, left, r, k);
        } else {
            return quickFind(nums, r + 1, right, k);

        }
    }

}
